using System;
using System.Collections.Generic;
using System.Text;
using Mono.Boost.PriorityQueue;

namespace Mono.Boost.Graph
{
    public class ShortestPath
    {
        public static void Djikstra(IGraph g, uint startVertex , IDictionary<uint, uint> Weight
                                    , out IDictionary<uint, uint> Cost
                                    , out IDictionary<uint, uint> ReversePath)
        {
            Cost= g.createVertexPropertyMap<uint>();
            ReversePath= g.createVertexPropertyMap<uint>();
            DictFibonacciHeap<uint> Q=new DictFibonacciHeap<uint>(Cost,(int)g.highestVertexId+1);
            Q.Insert((int)startVertex, 0);
            while (Q.Size != 0)
            {
#if Debug
                if (Cost.get(TopKey) != uint.MaxValue)
                    throw new exception("Djikstra Cost error");
                if (ReversePath.get(TopKey) != uint.MaxValue)
                    throw new exception("Djikstra Path error"); 
#endif
                foreach (EdgeInfo v in g.outgoing((uint)Q.TopKey))
                {
                    if (Cost.ContainsKey(v.v) && Cost[v.v] < Q.TopVal + Weight[v.id]) continue;
                    Q.SetVal((int)v.v,Q.TopVal + Weight[v.id]);
                    ReversePath[v.v] =(uint) Q.TopKey;
                }
                Q.Pop();
            }

        }

        public static void Djikstra(IGraph g, uint startVertex, IDictionary<uint, uint> Weight
                            , out IDictionary<uint, uint> Cost
                            , out IDictionary<uint, uint> ReversePath,int EndVertex)
        {
            Cost = g.createVertexPropertyMap<uint>();
            ReversePath = g.createVertexPropertyMap<uint>();
            DictFibonacciHeap<uint> Q = new DictFibonacciHeap<uint>(Cost, (int)g.highestVertexId + 1);
            Q.Insert((int)startVertex, 0);
            while (Q.Size != 0)
            {
#if Debug
                if (Cost.get(TopKey) != uint.MaxValue)
                    throw new exception("Djikstra Cost error");
                if (ReversePath.get(TopKey) != uint.MaxValue)
                    throw new exception("Djikstra Path error"); 
#endif
                if (Q.TopKey==EndVertex)
                        break;
                foreach (EdgeInfo v in g.outgoing((uint)Q.TopKey))
                {
                    if (Cost.ContainsKey(v.v) && Cost[v.v] < Q.TopVal + Weight[v.id]) continue;
                    Q.SetVal((int)v.v, Q.TopVal + Weight[v.id]);
                    ReversePath[v.v] = (uint)Q.TopKey;
                }
                Q.Pop();
            }

        }
    }
}
